A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Network devices referred to as routers are responsible for routing the packets through the packet-based network. The routers receive traffic from a wide variety of source devices and forward this traffic in accordance with various priorities. Usually, a service provider that owns the packet-based network provides various service levels to customers. For example, the service provider may offer a premium high bandwidth data service, a mid-range bandwidth data service and a low bandwidth data service. A customer subscribes to one of these service levels and the service provider provisions the routers to associate traffic originating from this customer's source device with the particular priority associated with the service level subscribed to by the customer. This priority ensures the customer receives the agreed upon bandwidth of the service level subscribed to by the customer.
In response to receiving a packet from the source device, the router first classifies the packet as originating from the source device and identifies the particular priority provisioned in the router for the source device. The router then typically stores the packet as one or more discrete data units referred to as “chunks” in one of a number of queues that is associated with the determined priority. The router services the queues in a manner that satisfies each of the defined priorities. For example, during operation, the router performs dequeue operations in accordance with the provisioned priorities to select chunks from the queues to schedule delivery of the packets. In some instances, the router executes multiple dequeue operations in an overlapping manner to concurrently select and service multiple queues. As one example, a router may implement dequeue and chunk scheduling operations in a pipelined fashion such that multiple chunks of a packet are being dequeued and scheduled for processing at any given point in time. By executing these dequeue operations concurrently, the router improves the number of chunks that can be serviced in a given amount of time. However, overlapping execution of these dequeue and scheduling operations may, in some instances, result in scheduling conflicts that waste processing resources and temporarily reduce packet throughput.